package tasks.zhuanyeji.微服务管理;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class 微服务管理 {

    public static int minServersNeeded(int[] memory, int maxCapacity) {
        if (memory.length <= 0 || maxCapacity <= 0) {
            return 0;
        }
        for (int i : memory) {
            if (i > maxCapacity) {
                return 0;
            }
        }
        Arrays.sort(memory);
        memory = reverseMemory(memory);
        List<Integer> servers = new ArrayList<>();

        for (int i : memory) {
            boolean isPackaged = false;
            for (int j = 0; j < servers.size(); j++) {
                Integer integer = servers.get(j);
                if (integer + i <= maxCapacity) {
                    servers.set(j, integer + i);
                    isPackaged = true;
                }
            }
            if (!isPackaged) {
                servers.add(i);
            }
        }

       return servers.size();
    }

    private static int[] reverseMemory(int[] memory) {
        int newMemory[] = new int[memory.length];
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < memory.length; i++) {
            list.add(memory[i]);
        }
        list.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 0; i < list.size(); i++) {
            newMemory[i] = list.get(i);
        }
        return newMemory;
    }
    public static void main(String[] args) {
        int[] memory = {4, 8, 1, 4, 2, 1};
        int maxCapacity = 8;

        int result = minServersNeeded(memory, maxCapacity);
        System.out.println("最少需要 " + result + " 台服务器"); // 输出：3
    }

}
